This invention relates to a method and apparatus for performing a modulo M translation on a large binary number and more particularly to a high speed method and reliable low-cost apparatus for performing the translation.
One area requiring such translation is in matrix calculations performed by large parallel memory array computers such as the one described by Budnik and Kuck in "The Organization and Use of Parallel Memories", IEE Translations on Computers, December 1971, pages 1566-1569. In such calculations a modulo 67 translation may be performed on a binary number in the order of 23 bits.
A straight forward modulo M translation of a large number is performed by dividing the number by M and storing the remainder as the answer. However, division of a large number is prohibitively slow and impractical for high-speed calculations.
Alternatively, by applying principles of residue arithmetic, a binary number of n bits may be represented as the sum of approximately weighted n binary bits. The modulo M residue may be determined beforehand for each of the n bits thereby permitting the binary to modulo M translation to be accomplished by n modulo M additions. However, n additions may be prohibitively slow for large values of n.